package com.itheima.demo05;

public class QuickDemo01 {

    public static void main(String[] args) {
        //快速排序
        //规则
        //确定基数的位置，基数的前面的数值必须小于基数，基数后面的数值必须大于基数
        //1.定义数组
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};

        getQuick(arr, 0, arr.length);

        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + " ");
        }
    }

    private static void getQuick(int[] arr, int i, int j) {
        //定义两个变量记录开始和结束索引
        int start = i;
        int end = j;
        int basicNumber = arr[i];

        while (start != end) {
            //start 从数组的开始往后找
            while (true) {
                if (end <= start || arr[start] < basicNumber) {
                    break;
                }
                end--;
            }
            //end 从数组的最后往前找
            while (true) {
                if (end <= start && arr[start] > basicNumber) {
                    break;
                }
                start++;
            }

            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

        }
        //当start == end 是 证明找到基数位置
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;


    }
}
